package com.caoyanan.algorithm.question.zuoTraining.training003.class08;

import com.caoyanan.algorithm.question.zuoTraining.LogarithmInputGenerator;

/**
 * 给定一个正数N，表示你在纸上写下1~N所有的数字
 * 返回在书写的过程中，一共写下了多少个1
 *
 * @author: caoyanan
 * @time: 2021/5/26 4:17 下午
 */
public class Question05_NumberOneCount {

    public static void main(String[] args) {
        //从1到630一共含有1的个数为:701 233 ，获取最高位是 n / Math.pow(10,k-1)，写成了 n % Math.pow(10,k-1)
        //从1到231一共含有1的个数为:160 154  ，从 32 到 231 的1个数，递归:146, 暴力:140 精确度问题  (int) ((k-1) * n / Math.pow(10,k-1) * Math.pow(10,k-2))  =>  (int)Math.pow(10,k-1) + (k-1) * n / (int)Math.pow(10,k-1) * (int)Math.pow(10,k-2);
        //从 52 到 351 的1个数，递归:170, 暴力:160, 运算顺序问题， (int)Math.pow(10,k-1) + (k-1) * n / (int)Math.pow(10,k-1) * (int)Math.pow(10,k-2) => (int)Math.pow(10,k-1) + (k-1) * ( n / (int)Math.pow(10,k-1) * (int)Math.pow(10,k-2));
        int i1 = oneCount(351);
        int[] arr = LogarithmInputGenerator.getInstance().generateRandomArray(1000, 50000);
        for (int i = 0; i < arr.length; i++) {
            int number1 = violentMethod(arr[i]);
            int number = oneCount(arr[i]);
            if (number != number1) {
                System.out.printf("从1到%s一共含有1的个数为:%s %s", arr[i], number, number1);
                System.out.println();
            }

        }
    }

    private static int violentMethod(int n) {

        int count = 0;
        for (int i = 1; i <= n; i++) {
            int number = i;
            while (number != 0) {
                if (number % 10 == 1) {
                    count ++;
                }
                number /= 10;
            }
        }
        return count;
    }

    /**
     * 求1数量，比如13625，f(13625) = km + f(3625) = km + km1 + f(625) ..
     * baseCase 当 n < 10时， return 1
     * 然后考虑非递归部分，比如求f(13625) 非递归部分为 3626~13625
     *  当最高位是1的时候，
     *      万位是1的数字有几个 10000~13625 3626个
     *      当数字是a，最高位是1，有k位。最高位是1的次数为 a % 10^(k-1) + 1
     *      千位是1的数字有几个？ 个位十位百位随便选，最高位总可以有一个对应值，使千位是1.比如 x1999、x1072，最高位都是1 。
     *      所以千位是1的数字 有 10^3 也就是 10^(k-2)
     *      同样的，百位，十位，个位是1的数字，也都是 (k-1) * 10^(k-2)个，
     *      整个为1的个数就是 a % 10^(k-1) + 1 + (k-1) * 10^(k-2)
     *  当最高位不是1的时候，比如求 f(3625) 非递归部分为 626~3625
     *      最高位是1的情况， 1000~1999，即有1000个
     *      即 数字是a，最高位不是1，有k位。 最高位是1的次数为 10^(k-1)
     *      百位为1的次数为， 11xx 21xx 31xx。300 即  a % 10^(k-1) * 10^(k-2)
     *      同样，十位是1的次数， 1x1x, 2x1x, 3x1x, 也是 300, 所以一共是 (k-1) * (a / 10^(k-1)) * 10^(k-2)
     *      整个为1的个数就是 10^(k-1) + (k-1) * (a / 10^(k-1)) * 10^(k-2)
     * @param n
     * @return
     */
    private static int oneCount(int n) {

        if (n == 0) {
            return 0;
        }
        if (n < 10) {
            return 1;
        }
        //求一个整数有几位
        int k = getLenOfNum(n);
        //最高位的值
        int f = (int) (n / Math.pow(10,k-1));

        int numberOne;
        if(f == 1) {
            numberOne = n % (int)Math.pow(10,k-1) + 1 + (k-1) * (int)Math.pow(10,k-2);
        } else {
            numberOne =  (int)Math.pow(10,k-1) + (k-1) * ( n / (int)Math.pow(10,k-1) * (int)Math.pow(10,k-2));
        }
        return numberOne + oneCount((int) (n % Math.pow(10,k-1)));
    }

    private static int getLenOfNum(int num) {
        int len = 0;
        while (num != 0) {
            len++;
            num /= 10;
        }
        return len;
    }
}
